\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  调试的时候模数记得用质数！
\item
  复杂度为 \(O(kp+logp)\)，\(k\) 是 \(n\) 转化为\(p\)进制后的位数
\end{itemize}

\begin{lstlisting}
ll  n, m, p;
ll Ext_gcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	ll ret = Ext_gcd(b, a % b, y, x);
	y -= a / b * x;
	return ret;
}
ll Inv(ll a, int m)   ///求逆元a相对于m
{
	ll d, x, y, t = (ll)m;
	d = Ext_gcd(a, t, x, y);
	if (d == 1) return (x % t + t) % t;
	return -1;
}
ll C(ll n, ll m, ll p)  ///组合数学
{
	ll a = 1, b = 1;
	if (m > n) return 0;
	while (m)
	{
		a = (a * n) % p , b = (b * m) % p;
		m-- , n--;
	}
	return (ll)a * Inv(b, p) % p; ///（a/b）%p 等价于 a*（b，p）的逆元
}
// Lucas（n，m，p）=C（n%p，m%p，p）*Lucas（n/p，m/p，p）；   ///这里可以采用对n分段递归求解，
// Lucas（x，0，p）=1；
int Lucas(ll n, ll m, ll p)  ///把n分段递归求解相乘
{
	if (m == 0) return 1;
	return (ll)C(n % p, m % p, p) * (ll)Lucas(n / p, m / p, p) % p;
}
signed main()
{
	int T = 1;
	cin >> T;
	while(T --)
	{
		cin >> n >> m >> p;
		cout << Lucas(n + m , m , p) << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
